<?php
/**
 * @category Goatherd
 * @package Goatherd\Commons
 *
 * @author Copyright (c) 2012 Maik Penz <maik@phpkuh.de>
 * @version $Id: Trie.php 106 2012-06-15 21:11:38Z maik@phpkuh.de $
 *
 * This file is part of Goatherd library.
 *
 * Goatherd library is free software: you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Goatherd library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Goatherd library. If not, see <http://www.gnu.org/licenses/>.
 */
namespace Goatherd\Commons\Word;

/**
 * Trie implementation (http://en.wikipedia.org/wiki/Trie).
 *
 * Class can be easily extended to hold payload.
 *
 * @todo unit test
 * @todo remove cslashes at word retrieval/ iteration step(s)
 * @todo performance test for has() with and without references
 *
 * @package Goatherd\Commons
 * @subpackage Word
 */
class Trie
implements ITrie, \Serializable, \Iterator
{
    /**
     * End of word flag.
     *
     * @var integer
     */
    const END_OF_WORD = 0;

    /**#@+
     * @var int - iterator keys (internal use)
     */
    const IT_NODE = 0;
    const IT_PATH = 1;
    const IT_NEXT = 2;
    /**#@-*/

    /**
     * root container
     *
     * @var array
     */
    protected $_trie = array();

    /**
     * Letter sort order (as used by getWords() method).
     *
     * @var integer
     */
    protected $_sort = SORT_LOCALE_STRING;

    /**
     * Iterator path pointer.
     *
     * @var array
     */
    protected $_current = false;

    /**
     * Iterator node path.
     * Format: array(array &$node, string $key)
     *
     * @var array
     */
    protected $_path = array();

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::add()
     */
    public function add(&$word)
    {
        // prepare
        $letters = $this->split($word);
        $lastLetter = array_pop($letters);

        $node = &$this->_trie;
        // add nodes as needed
        foreach ($letters as $letter) {
            if (isset($node[$letter])) {
                // extend leaf
                $node[$letter] === true
                and $node[$letter] = array(self::END_OF_WORD => true);
            } else {
                // new node
                $node[$letter] = array();
            }
            // traverse
            $node = &$node[$letter];
        }

        // mark end-of-word
        if (!isset($node[$lastLetter])) {
            $node[$lastLetter] = true;
        } elseif (is_array($node[$lastLetter])) {
            $node[$lastLetter][self::END_OF_WORD] = true;
        } // else child node is end-of-word
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::addAll()
     */
    public function addAll(&$words)
    {
        foreach ($words as $word) {
            $this->add($word);
        }
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::has()
     */
    public function has($word)
    {
        $letters = $this->split($word);
        $node = &$this->_trie;
        foreach ($letters as $letter) {
            if (!isset($node[$letter])) {
                return false;
            }
            $node = &$node[$letter];
        }

        return $node === true || isset($node[self::END_OF_WORD]);
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::getWords()
     */
    public function getWords()
    {
        $list = array();
        foreach ($this as $word) {
            $list[] = $word;
        }

        return $list;
    }

    /**
     *
     * @return \Goatherd\Commons\Word\TreeIterator
     */
    public function getIterator()
    {
        return new TreeIterator($this);
    }


    /**
     * Count nodes.
     *
     * @return integer
     */
    public function nodeCount()
    {
        $count = 0;
        $this->_nodeCount($this->_trie, $count);
        return $count;
    }

    /**
     * Count words (end-of-word flags).
     *
     * @return integer
     */
    public function wordCount()
    {
        $count = 0;
        $this->_wordCount($this->_trie, $count);
        return $count;
    }

    /**
     * Get/ set sort ordering (see sort() function).
     *
     * @param integer|false $order        [=null]
     * @return integer
     */
    public function sortOrder($order = null)
    {
        $oldOrder = $this->_sort;

        if ($order !== null) {
            $this->_sort = $order;
        }

        return $oldOrder;
    }

    /**
     *
     * @return array
     */
    public function getRoot()
    {
        return $this->_trie;
    }

    /**
     *
     * @param array $root
     */
    public function setRoot(array $root)
    {
        $this->_trie = $root;
        return $this;
    }

    /**
     *
     * @return string
     */
    public function serialize ()
    {
        $serialized = serialize($this->getRoot());

        return $serialized;
    }

    /**
     *
     * @param string $serialized
     */
    public function unserialize ($serialized)
    {
        $root = unserialize($serialized);
        $this->setRoot($root);
    }

    /**
     * Split logic.
     * @todo does input need normalisation?
     *
     * @param string $word
     */
    public function split(&$word)
    {
        // preg split is faster than str_split anyway
        $word = addcslashes($word, '0123456789');
        $letters = preg_split('/(?<![\\\\])|(?![\d])/u', $word, null, PREG_SPLIT_NO_EMPTY);

        return $letters;
    }

    /**
     * Get node children.
     * @todo test performance of child listing
     *
     * @param array $node
     * @param boolean $sorted [=false]
     * @return array
     */
    public function &getChildren(array &$node, $sorted = false)
    {
        $keys = array_diff(array_keys($node), array(0,1,2,3,4,5,6,7,8,9));
        $sorted and ($this->_sort === false or ksort($keys, $this->_sort));
        $children = array();
        foreach ($keys as $key) {
            $children[$key] =& $node[$key];
        }
        return $children;
    }

    /**
     *
     * @param array $node
     * @param int $count
     */
    protected function _nodeCount(&$node, &$count)
    {
        $children = $this->getChildren($node);
        foreach ($children as &$child) {
            $child === true or $this->_nodeCount($child, $count);
        }
        $count ++;
    }

    /**
     * (non-PHPdoc)
     * @see Iterator::current()
     */
    public function current ()
    {
        return $this->_path[$this->_current][self::IT_PATH];
    }

    /**
     * (non-PHPdoc)
     * @see Iterator::next()
     */
    public function next ()
    {
        $current = $this->_current;
        // end-of-tree
        if ( !$current ) {
            return ;
        }

        // check path for further children (bottom-top)
        while ( isset($this->_path[$current]) ) {
            $node = &$this->_path[$current];
            if ( !is_array($node[self::IT_NEXT]) ) {
                unset($this->_path[$current]);
                $current--;
                continue;
            }
            // has children
            do {
                // try next child
                $child = current($node[self::IT_NEXT]);
                if ( $child === false ) {
                    unset($this->_path[$current]);
                    $current--;
                    continue 2;
                }
                $key = key($node[self::IT_NEXT]);
                // iterate children
                next($node[self::IT_NEXT]);
                // only use valid keys
            } while (is_int($key));

            // iterate
            $this->_current = ++$current;
            $keyPath = $node[self::IT_PATH];
            $keyPath[] = $key;

            // leaf
            if ($child === true) {
                $this->_path[$current] = array(
                        self::IT_PATH => $keyPath,
                        self::IT_NEXT => false,
                );
                return ;
            }

            // prepare internal node for traversal
            reset($child);
            $this->_sort and ksort($child, $this->_sort);
            // queue
            $this->_path[$current] = array(
                    self::IT_PATH => $keyPath,
                    self::IT_NEXT => $child,
            );

            // return on end-of-word
            if ( isset($child[self::END_OF_WORD]) ) {
                return ;
            }
        }

    }

    /**
     * Length of current key (of iterator)
     *
     * @return integer
     */
    public function getCurrentKeyLength()
    {
        return $this->_current;
    }

    /**
     * (non-PHPdoc)
     * @see Iterator::key()
     */
    public function key ()
    {
        return $this->_path[$this->_current][self::KEY];
    }

    /**
     * (non-PHPdoc)
     * @see Iterator::valid()
     */
    public function valid ()
    {
        return isset($this->_path[$this->_current]);
    }

    /**
     * (non-PHPdoc)
     * @see Iterator::rewind()
     */
    public function rewind ()
    {
        // set iteration root, sort if defined to do so
        reset($this->_trie);
        $this->_path = array(
                1 => array(
                        self::IT_PATH => array(),
                        self::IT_NEXT => $this->getChildren($this->_trie, $this->_sort),
                ),
        );
        $this->_current = 1;

    }

    /**
     *
     * @param array $node
     * @param int $count
     */
    protected function _wordCount(&$node, &$count)
    {
        $children = $this->getChildren($node);
        foreach ($children as &$child) {
            if ($child === true) {
                $count++;
            } else {
                $this->_wordCount($child, $count);
            }
        }
        isset($node[self::END_OF_WORD]) and $count ++;
    }
}